/*
 * @lc app=leetcode.cn id=556 lang=typescript
 *
 * [556] 下一个更大元素 III
 */

// @lc code=start
function nextGreaterElement(n: number): number {
  const max = 2 ** 31 - 1;
  const nums = [...String(n)];
  const reverse = (nums: string[], begin: number) => {
    let i = begin;
    let j = nums.length - 1;
    while (i < j) {
      [nums[i], nums[j]] = [nums[j], nums[i]];
      i++;
      j--;
    }
  };

  // 尽量靠右的较小数
  let i = nums.length - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) {
    i--;
  }

  if (i < 0) return -1;

  // 比较小数稍大一点的数字
  let j = nums.length - 1;
  while (j >= 0 && nums[i] >= nums[j]) {
    j--;
  }
  [nums[i], nums[j]] = [nums[j], nums[i]];
  // 反转右边为升序序列
  reverse(nums, i + 1);

  const ans = Number(nums.join(''));

  return ans > max ? -1 : ans;
}
// @lc code=end
